Modular Arithmetic

Modular arithmetic is concerned with the arithmetic of remainders from division.

Modulo Reduction

Dividing by can be written as , where is the quotient and is the remainder. The modulo operation (%) returns the remainder when dividing by . Programmatically, this is written as a % N and the mathematical equivalent is .

Mapping an integer to its remainder upon division by some number is known as reduction modulo and boils down to mapping the integer to an integer between and .

Modulo Congruence

Two numbers are said to be congruent modulo , written as (terrific notation, mathematicians) if they have the same remainder when dividing by , i.e. . The good thing about modulo congruence is that it under addition, subtraction and multiplication:

Modulo Inversion

If there is an integer such that , then is said to be invertible modulo and is said to be a (multiplicative) inverse of modulo . A given integer may have many multiplicative inverses - for example, it is fairly easy to show that if is a multiplicative inverse of , then so is and if is yet another inverse of , then . For simplicity, the multiplicative inverse of which is in the range is denoted by .

Modulo division by can then be defined as multiplication by and this gives the following nice property:

Groups

A group is simply a set equipped with a group operation which satisfy the following properties:

Closure: For all ,
Identity: There exists an identity element such that for all
Invertibility: For each there exists an inverse element such that
Associativity: For all

A group whose operation also supports commutativity (i.e., ) is called abelian.

The order of a group, denoted by , is the number of elements in the group.

Additive vs Multiplicative Notation

The group operation is often denoted in a different way.

Additive notation uses the sign for its group operation, i.e. . However, this does not mean that the group's operation is necessarily addition. The identity element here is denoted by and the inverse of an element is written as . Applying the group operation to a single element a total of times is denoted as

Note that is an integer while is an element of the group and so is not the group operation applied between and .

Multiplicative notation denotes the group operation either by or by . Once again, this does not mean that the group operation is necessarily multiplication - it is simply written this way. The identity element here is denoted by and the inverse of an element is written as . Applying the group operation to a single element a total of times is denoted via exponentiation:

Once again, is an integer and not a member of the group. This is useful notation because it truly "behaves" like exponentiation in regards to its properties: and . Furthermore, if the group is abelian, then for all it holds that .

Some Facts about Groups

For all $a,b,c \in \mathbb{G}$, if $a\circ c = b \circ c$, then $a = b$ and in particular, if $ac = c$, then $a$ is the identity element of $\mathbb{G}$.

TODO

Interestingly, if the group is finite and , applying the group operation a single element number of times, then we get the identity element.

For any finite group $\mathbb{G}$ and element $g \in \mathbb{G}$, it holds that g^{|\mathbb{G}|} = 1$.

TODO

As a corollary of this, it turns out that applying the group operation to the same element more than times has the same effect as doing it times which brings computational benefits.

For any finite group $\mathbb{G}$ with $|\mathbb{G}| \gt 1$ and any $g \in \mathbb{G}$, it holds that $g^x = g^{[x \mod |\mathbb{G}|]}$

The Groups and

The abelian group denotes the set of integers equipped with addition modulo as its group operation. The closure property is trivially satisfied because modulo reduction produces a number in the range . Similarly, associativity and commutativity follow from the fact that integers have these properties. The identity element is . Since , it follows that the inverse of any element is .

We would like to have a similar group but with multiplication modulo as the group operation. However, this is not trivial to do because even non-zero elements in might lack an inverse. It turns out that the elements in which are invertible modulo are precisely those integers which are relatively prime with . Therefore, we can define the set for as follows:

We equip this set with the operation multiplication modulo to yield the abelian group .

Cyclic Groups

For any , where is some finite group, consider the following set:

We know for sure that . Let be the smallest positive integer such that . We know then that the sequence repeats every elements, i.e. , etc. Therefore,

It is not hard to verify that is a subgroup of of order and is thus said to be generated by . The integer is also sometimes simply referred to as the order of the element .

There are some interesting properties of such elements.

For any element $g$ of order $i$ in the finite group $\mathbb{G}$, it holds that $g^x = g^y$ if and only if $x = y \mod i$.

TODO

The order $i$ of any element $g$ in a finite group $\mathbb{G}$, must be a factor of the group order, i.e. $i | m$, where $m$ is the order of $\mathbb{G}$.

TODO

A group $\mathbb{G}$ is called *cyclic* if all of its elements can be obtained by applying the group operation repetitevely to *one* of its elements.

The group is called cyclic, if there is an element of order . Such an element is called a generator of . Therefore, any element is equal to for some - the group has elements and so does the group and since is a subgroup of , then they must contain the exact same elements.

Cyclic groups have some interesting properties.

Any group $\mathbb{G}$ with a prime order $p$ is cyclic and all of its elements, except for the identity, are its generators.

The group order $p$ *must* be divisible by the order $i$ of any element and so $i = p$ or $i = 1$. Only the identity element has order $1$ and so all the other elements must be of order $p$ and are therefore generators of the group.

An immediate corollary of this theorem is that the group , where is some prime number, is a cyclic group of order .